package 动态规划.背包问题;

import java.util.Scanner;

/**
 * 01背包问题(拿或者不拿)
 * 一个旅行者有一个最多能装m公斤的背包，现有n件物品，它们的重量分别是W1,W2...,Wn它们的价值分别是C1,C2...Cn,求旅行者能获得的最大总价值(每个物品只能拿一次)
输入样例：
10 4
2 1
3 3
4 5
7 9
 * */

public class _01背包问题 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int[][] dp=new int[n+1][m+1];
		int[] w=new int[n+1];
		int[] c=new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			c[i]=sc.nextInt();
		}
		/*======dp表========*/
		for(int x=1;x<=n;x++)
			for(int y=1;y<=m;y++) {
				if(y<w[x])	//如果在容量为y的情况拿不下第x件物品，那么背包的价值就等于上一个
					dp[x][y]=dp[x-1][y];
				else
					//（重点）状态转移方程式
					dp[x][y]=max(dp[x-1][y],dp[x-1][y-w[x]]+c[x]);	//如果拿的下，要判断是否值得拿
			}
		/*有没有发现，dp表每一行都只和上一行有关，很多行都是只会用一次。我们可以对其进行优化*/
		/*=======输出dp表========*/
		for(int i[]:dp) {
			for(int j:i) {
				System.out.print(j+" ");
			}
			System.out.println();
		}
//		System.out.println("最多能拿"+dp[n][m]+"元");
		System.out.println(dp[n][m]);
	}

	private static int max(int i, int j) {
		return i>j?i:j;
	}

}